import java.util.HashMap;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution377 {

    public static void main(String args[]) {
        Solution377 s = new Solution377();
        System.out.println(s.combinationSum4(new int[]{1, 2, 3}, 4));
    }

    HashMap<Integer, Integer> mp = new HashMap<>();

    public int combinationSum4(int[] nums, int target) {
        return dfs(nums, target);
    }


    public int dfs(int nums[], int t) {
        if (mp.containsKey(t)) {
            return mp.get(t);
        }

        if (t == 0) {
            return 1;
        } else if (t > 0) {

            int ret = 0;
            for (int i = 0; i < nums.length; i++) {
                ret += dfs(nums, t - nums[i]);
            }
            mp.put(t, ret);
            return ret;
        } else {
            return 0;
        }
    }

}



















